Nedeterministički konačni automat

U teoriji izračunljivosti, nedeterministički konačni automat (NKA) (još i nedeterministički konačni stroj) je konačni automat u kojem za svaki par stanja i ulaznog znaka (simbola) može postojati nekoliko mogućih sljedećih stanja.

Intuitivna objašnjenja

NKA obrađuje niz ulaznih znakova. Za svaki ulazni znak obavlja prijelaz u novo stanje sve dok svi ulazni znakovi nisu obrađeni.

Zovemo ga nedeterminističkim zato jer se može dovesti u situaciju da postoje višestruki prijelazi iz trenutnog stanja koristeći isti znak. Za ε-NKA je također moguć prijelaz u novo stanje bez čitanja ulaznog znaka uopće. Na primjer, ako je neki fiktivni ε-NKA trenutno u stanju 1, a sljedeći ulazni znak jest a, on može preći u stanje 2 bez da obradi ijedan ulazni znak, kao i ući u stanje 3 čitanjem znaka a. NKA ne može odrediti koji je korektan prijelaz koji treba obaviti, te stoga ulazi u oba stanja.

Promjene stanja ε-NKA, a da se pri tome ne pročita ulazni znak, zovemo epsilon-prijelazi ili lambda-prijelazi. Obično se označavaju grčkim slovima ε ili λ.

Kada NKA pročita sve znakove ulaznog niza, on prihvaća niz ako i samo ako postoji neki slijed prijelaza koje može načiniti a koji će ga dovesti u prihvatljivo stanje. Shodno tome, ne prihvaća (odbija) niz znakova ako bez obzira koje izbore učini prilikom prijelaza u neki element skupa od više stanja, neće završiti u nekom od prihvatljivih stanja.

Formalna definicija

Nedeterministički konačni automat (NKA) se formalno definira kao uređena petorka, $\left(Q,\Sigma ,\delta ,q_{0},F\right)$, koju čini:

• konačni skupa stanja ($Q$)
• konačni skup ulaznih znakova zvan ulazna abeceda ($\Sigma$)
• funkcija prijelaza ($\delta :Q\times \Sigma \to P(Q)$)
• početno (ili inicijalno) stannje ($q_{0}\in Q$)
• istaknuti skup stanja $F$ kojeg zovemo skup prihvatljivih (ili finalnih) stanja ($F\in Q$)

pri čemu je $P(Q)$ partitivni skup (skup svih podskupova) skupa $Q$, $\varepsilon$ prazni niz, a $\Sigma$ ulazna abeceda

Neka je M NKA takav da M = $\left(Q,\Sigma ,\delta ,q_{0},F\right)$, i X je niz znakova nad abecedom $\Sigma$. M prihvaća niz X ako postoji i reprezentacija niza X oblika $x_{1}x_{2}...x_{n},x_{i}\in \left\{{\Sigma \cup \varepsilon }\right\}$, i slijed prijelaza stanja $r_{0},r_{1},...,r_{n},r_{i}\in Q$ koji zadovoljava sljedeće uvjete:

1. $r_{0}=q_{0}$
2. $r_{i}=\delta (r_{i-1},x_{i})$ za $i=1,...,n-1$
3. $r_{n}\in F$

Stroj započinje rad u proizvoljnom početnom stanju te potom čita niz znakova svoje ulazne abecede. Automat koristi relaciju prijelaza T da odredi sljedeće stanje koristeći trenutno stanje te znak upravo pročitan ili prazni niz (u slučaju ε-prijelaza). Međutim, sljedeće stanje NKA ne ovisi samo o trenutnom ulaznom događaju (tj. trenutno pročitanom znaku), već i o proizvoljnom broju narednih ulaznih događaja. Sve dok se ti sljedeći ulazni događaji ne dogode (tj. znakovi se ne pročitaju), nije moguće odrediti stanje u kojem se stroj nalazi. Ako se po završetku čitanja ulaznog niza automat nalazi u prihvatljivom stanju, kažemo da NKA prihvaća niz, inače kažemo da ga ne prihvaća (odbija).

Skup svih nizova znakova koje NKA prihvaća zovemo jezikom koji NKA prihvaća. Taj jezik je regularni jezik.

Za svaki NKA može biti konstruiran istovjetni DKA, tj. DKA koji prihvaća isti jezik. Stoga je moguće obaviti konverziju već postojećeg NKA u DKA u svrhu implementiranja (možebitno) jednostavnijeg stroja. Takva konverzija može dovesti do eksponencijalnog rasta u broju potrebnih stanja stroja.

Ostvarenje

Postoji mnogo načina za ostvarenje NKA:

• Konvertiraj u istovjetni DKA. U nekim će slučajevima doći do eksponencijanog rasta u veličini automata (posebice broju potrebnih stanja) a time i pomoćnog prostora proporcionalnog broju stanja NKA (s obzirom da pohrana vrijednosti stanja zahtijeva najviše jedan bit za svako stanje NKA).
• Održavaj podatkovnu strukturu skup (konačni asocijativni kontejner bez ponavljanja vrijednosti) koja će sadržavati sva stanja u kojima stroj trenutno može biti. Prilikom čitanja posljednjeg ulaznog znaka, ukoliko je jedno od stanja konačno stanje, stroj prihvaća niz znakova. U najgorem slučaju, ovo može zahtijevati pomoćni prostor veličine proporcionalne broju stanja NKA; ako podatkovna struktura skup koristi točno jedan bit po stanju NKA, ovo ostvarenje je istovjetno prethodnom.
• Stvaramo višestruke kopije. Za svaku odluku o grananju u n stanja, NKA kreira do $n-1$ kopija stroja. Svaka kopija ulazi u odvojeno stanje. Ako se, prilikom čitanja posljednjeg ulaznog znaka, barem jedna kopija NKA nalazi u prihvatljivom stanju, NKA prihvaća ulazni niz znakova. (Ovo ostvarenje također zahtijeva linearni prostor za pohranu s obzirom na broj stanja NKA, budući da može biti postojati po jedan stroj za svako stanje NKA).
• Eksplicitno propagiraj pojedine znakove kroz prijelaznu strukturu NKA i zabilježi kadgod znak dosegne prihvatljivo stanje. Ovo je ponekad korisno kad NKA treba enkodirati dodatni kontekst o događajima koji su potaknuli prijelaz. (Za programsko ostvarenje ove tehnike koja prati reference na objekt pogledati papir koji je implementira pod nazivom Tracematches.)

Primjer

Sljedeći primjer objašnjava NKA M koji operira nad binarnom abecedom i koji odlučuje sadrži li ulazni niz znakova paran broj znamenki 0 ili paran broj znamenki 1.

M = $\left(Q,\Sigma ,\delta ,q_{0},F\right)$ gdje je

• $\Sigma =\left\{{0,1}\right\}$
• $Q=\left\{{S_{0},S_{1},S_{2},S_{3},S_{4}}\right\}$
• $q_{0}=S_{0}$
• $F=\left\{{S_{1},S_{3}}\right\}$, te
• Funkcija prijelaza $\delta$ može biti definirana sljedećom tablicom prijelaza:

	0	1	ε
S0	{}	{}	{S1, S3}
S1	{S2}	{S1}	{}
S2	{S1}	{S2}	{}
S3	{S3}	{S4}	{}
S4	{S4}	{S3}	{}

Dijagram stanja za M jest:

M se može shvatiti kao unija dva DKA: jednog sa skupom stanja {S₂, S₁} i drugog sa skupom stanja {S₃, S₄}.

Jezik automata M može biti opisan sljedećim regularnim izrazom:

$(1^{*}(01^{*}01^{*})^{*})\cup (0^{*}(10^{*}10^{*})^{*})$

Povezano

• Deterministički konačni automat

Izvori

• Michael Sipser. Introduction to the Theory of Computation. PWS, Boston. 1997. ISBN 0-534-94728-X. Section 1.2: Nondeterminism, pp.47–63.
• Siniša Srbljić. Jezični Procesori. Element, Zagreb. 2003. ISBN 953-197-129-3. Sekcija 2.1.3: Nedeterministički konačni automat (NKA), pp.29–34.